package com.atwulidun.prim06;

import java.util.Arrays;

public class Prim {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵的关系使用二维数组表示,10000 这个大数，表示两个点不联通
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}};
        // 创建一个图对象
        Graph graph = new Graph(data.length, data, weight);
        // 调用prim方法
        MinTree.prim(graph, 6);
    }
}

// 最小生成树类
class MinTree {
    // prim算法，得到最小生成树
    // v表示从第v个顶点开始生成：'A'->0，'B'->1，...
    public static void prim(Graph graph, int v) {
        // 定义一个标记顶点是否被访问过的一维数组
        int[] isVisited = new int[graph.getVerNum()];
        // 把v标记为已经访问
        isVisited[v] = 1;
        // 定义两个变量来标记顶点的下标
        int h1 = -1, h2 = -1;
        // 定义一个变量来保存边的最小权重，10000表示两个顶点之间不连通
        int minWeight = 10000;
        // 接下来是三个for循环
        // 第一层循环用来生成边，边的条数为顶点的个数-1，因此i从1开始
        for (int i = 1; i < graph.getVerNum(); i++) {
            // 第二层循环用来找已经被访问过的顶点
            for (int j = 0; j < graph.getVerNum(); j++) {
                // 第三层循环用来找还没有被访问过的顶点
                for (int k = 0; k < graph.getVerNum(); k++) {
                    if (isVisited[j] == 1 && isVisited[k] == 0 && graph.getWeight()[j][k] < minWeight) {
                        minWeight = graph.getWeight()[j][k];
                        // 把该条边的两个下标记录下来
                        h1 = j;
                        h2 = k;
                    }
                }
            }
            // 这里找到一条边了，将找到的边和其对应的权重打印出来
            System.out.println("边：<" + graph.getData()[h1] + "," + graph.getData()[h2] + ">，权重：" + graph.getWeight()[h1][h2]);
            // 在找下一条边之前先把minWeight重置
            minWeight = 100000;
            // h1,h2可以不用重置
            // 最最重要，最容易漏的一步：把h2标记为已被访问！！！！！！！！！！！！！！！！！！！！！！！！！！
            isVisited[h2] = 1;
        }
    }
}

// 图类
class Graph {
    // 顶点的个数
    private int verNum;
    // 保存顶点值的一维数组
    private char[] data;
    // 保存边权值的邻接矩阵
    private int[][] weight;

    public Graph(int verNum, char[] data, int[][] weight) {
        this.verNum = verNum;
        this.data = data;
        this.weight = weight;
    }

    // 打印图的方法
    public void show() {
        for (int[] ints : weight) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public int getVerNum() {
        return verNum;
    }

    public void setVerNum(int verNum) {
        this.verNum = verNum;
    }

    public char[] getData() {
        return data;
    }

    public void setData(char[] data) {
        this.data = data;
    }

    public int[][] getWeight() {
        return weight;
    }

    public void setWeight(int[][] weight) {
        this.weight = weight;
    }
}
